package org.totoro.structure.list.impl;

import org.totoro.structure.list.List;

import java.util.Objects;
import java.util.Optional;

/**
 * 单向链表
 *
 * @author daocr
 * @date 2020/3/22
 */
public class UnidirectionalLinkedList<E> implements List<E> {

    /**
     * 总大小
     */
    private int size;


    /**
     * 最后节点指针
     */
    private Node<E> lastNode;

    /**
     * 头结点
     */
    private Node<E> firstNode;

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size + 1;
    }

    @Override
    public boolean contains(E o) {
        return indexOf(o) != -1;
    }

    @Override
    public boolean add(E element) {

        Node<E> nowElementNode = new Node<>(element);

        if (firstNode == null) {
            lastNode = nowElementNode;
            firstNode = nowElementNode;
            return true;
        }

        lastNode.next = nowElementNode;
        lastNode = nowElementNode;
        size++;
        return true;
    }

    @Override
    public void add(int index, E element) {

        outOfBound(index);

        Node<E> newNode = new Node<>(element);
        // 特殊处理下标为0
        Node<E> nodeElement = getBeforeElement(index == 0 ? 0 : index - 1);

        // 如果要插入头结点
        if (nodeElement == firstNode) {
            Node<E> next = firstNode;
            firstNode = newNode;
            newNode.next = next;
            return;
        }

        Node<E> next = nodeElement.next;
        newNode.next = next;
        nodeElement.next = newNode;

        size++;

    }

    @Override
    public int indexOf(E o) {

        Node<E> pointer = firstNode;

        int index = 0;
        while ((pointer != null)) {
            if (Objects.equals(pointer.element, o)) {
                return index;
            }
            pointer = pointer.next;
            index++;
        }

        return -1;
    }


    @Override
    public int lastIndexOf(E o) {
        return 0;
    }

    @Override
    public boolean remove(E e) {

        Node<E> curPointer = firstNode;
        Node<E> beforeNode = firstNode;
        while ((curPointer != null)) {

            if (Objects.equals(e, curPointer.element)) {

                if (curPointer == firstNode) {
                    // 垃圾回收
                    firstNode.element = null;
                    Node<E> next = firstNode.next;
                    firstNode = next;
                    size--;
                    return true;
                }

                if (curPointer == lastNode) {
                    // 垃圾回收
                    lastNode.element = null;
                    lastNode = beforeNode;
                    size--;
                    return true;
                }
                // 垃圾回收
                curPointer.element = null;
                beforeNode.next = curPointer.next;
                size--;
                return true;

            }

            beforeNode = curPointer;
            curPointer = curPointer.next;

        }

        return false;
    }

    @Override
    public E get(int index) {

        outOfBound(index);

        Node<E> element = getBeforeElement(index);

        return Optional.ofNullable(element).map(e -> e.element).orElse(null);
    }

    private Node<E> getBeforeElement(int index) {

        Node<E> pointer = firstNode;
        int whileIndex = 0;

        while ((pointer != null)) {

            if (whileIndex == index) {
                return pointer;
            }

            pointer = pointer.next;
            whileIndex++;
        }

        return null;
    }


    private void outOfBound(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index:" + index);
        }
    }

    /**
     * 节点信息
     *
     * @param <E>
     */

    public static class Node<E> {

        public Node(E element) {
            this.element = element;
        }

        private Node<E> next;

        private E element;

    }

    @Override
    public E getLast() {

        if (isEmpty()) {
            return null;
        }
        return lastNode.element;
    }

    @Override
    public void addLast(E element) {
        add(element);
    }

    public static void main(String[] args) {

        UnidirectionalLinkedList<String> stringArrayList = new UnidirectionalLinkedList<>();


        for (int i = 0; i < 10; i++) {
            stringArrayList.add(String.valueOf(i));
        }

        print(stringArrayList);

        stringArrayList.remove("2");

        print(stringArrayList);


    }

    private static void print(UnidirectionalLinkedList<String> stringArrayList) {
        int size = stringArrayList.size();

        for (int i = 0; i < size; i++) {
            System.out.print(stringArrayList.get(i));
        }

        System.out.println();
    }

}
